package com.zx.练习题._2022面试题收集;

import com.zx._12_算法.LinkNode;

public class 链表的对折 {

    public static void main(String[] args) {
        LinkNode node0 = run(LinkNode.getNodes(1, 2, 3, 4, 5, 6));
        node0.print();

        LinkNode node1 = run(LinkNode.getNodes(1, 2, 3, 4, 5));
        node1.print();

        LinkNode node2 = run(LinkNode.getNodes(1, 2, 3, 4));
        node2.print();

        LinkNode node3 = run(LinkNode.getNodes(1, 2));
        node3.print();

        LinkNode node4 = run(LinkNode.getNodes(1));
        node4.print();


    }

    public static LinkNode run(LinkNode head) {
        // 快慢指针，找到中间位置
        LinkNode l1 = head;
        LinkNode l2 = head;

        while (l2.next != null && l2.next.next != null) {
            l1 = l1.next;
            l2 = l2.next.next;
        }
        // mid 是前面的最后一个，不要反转
        LinkNode mid = l1;

        // 反转后面的
        LinkNode newHead = res(mid.next);

        // 前后对接
        mid.next = newHead;

        return head;
    }

    public static LinkNode res(LinkNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 指针
        // 上一个
        LinkNode last = head;
        // 当前
        LinkNode cur = head.next;
        last.next = null;

        while (true) {
            // 把下一个先保存出来
            LinkNode next = cur.next;

            cur.next = last;

            if (next == null) {
                break;
            }
            last = cur;
            cur = next;
        }

        return cur;
    }
}
